Batch 3 - Class 142 - Induction II, Visualization

• How many squares does a 5x5 grid have? You have solved this problem before, but can you attempt it by induction? Can you generalize it for nxn square?

• Answer: 1^2+2^2+3^2+4^2+5^2 
• Base case: 1x1 grid has only 1 square
• Induction Hypothesis: nxn grid has squares equal to sum of squares of first n natural numbers
• Induction Step: Assume nxn grid has the defined number of squares. Now lets add the (n+1)th row and column and try to count all the "new squares" this formed. It will incrementally be (sum of first n+1 natural numbers)+(sum of first n natural numbers) i.e. (n+1)^2.
• The easy way to look at the above sum (visually) is to see it as diagonals of a (n+1) x (n+1) square!

• Can you find another visual solution to the above problem? Let us try to locate the left bottom for all 1x1 squares, then for all 2x2 squares and so on

• On the 5x5 grid, we will now start from a particular square and try to visit every square without repeating a square. From any given square, you are allowed to go to one of the adjacent four squares. Hence a possible path is as under

• Try starting from a different position. Are you still able to traverse all the squares?
• Are there any starting positions for which you are unable to traverse the whole grid?
• Do you think if you tried other possible ways, you would get there? Try harder.
• Are there starting positions from which you think its impossible to traverse all squares? Can you prove that its impossible?
• Instructor Notes: Let kids work on the problem at this stage, and let them come up with their insights. Some may get to a pattern, some may not. If they don't, provide a hint for them to try and spot a pattern on which starting points are good versus bad. Note the application of symmetry in getting to the pattern.

• What does the pattern look like? Does it provide a hint into how to make a conclusive proof about the cells marked as question marks?
• Instructor Notes: At this stage, it is a bit of an epiphany. See if kids can get to checkerboard pattern. If they can, then provide them a hint to chessboard coloring. Second hint is to think about what happens to the color in each move. Third is to count number of black and white cells - ask kids to list the "paths" as sequence of black and white cells. That should do it.
• Back to Induction - What would happen in a 4x4 or a 6x6 grid? Does the fact that now you have equal number of black and white squares automatically imply that such a path is always possible?
• Answer: No. Ask students for an example of a grid where there are equal number of black and white squares, but a path is not possible. Answer: 6x1 strip
• Can you provide and an even square grid always has such paths from all starting positions?
• Hint: Use induction
• Answer: Essentially, starting from any position on outermost squares, one can complete the full outer round, and then enter inside - if a smaller even grid had solutions, this must as well. If you are starting from an inner starting square, do what you would do for n-2 grid. At some point in this solution you would be going along the "edge" of n-2 grid (note that this is mandatorily required to approach the corner of inside n-2 grid). This can be used as an opportunity to jump to outermost layer and complete that before coming back in.
• Why doesn't this apply for odd grids. For example, 1x1 grid has a trivial solution. Why doesn't that scale to all odd grids? See what happens when you go to 3x3. Here, starting on outermost and completing a full round, we have no point of entry to inner squares. We need at least 4 square-side to guarantee that. Induction can sometimes mislead, so be careful!
• Also note that the converse is not true. There could have been a solution to 5x5 even if solutions to 3x3 did not exist. So induction works one way only. This is because we go from n to n+1 in induction, and not from n+1 to n.
• Arjun had a stronger claim and a beautiful solution to this problem. The claim being that there is a loop across all squares, with one leg of the loop along a full side of the grid. Given the loop, you can start from any square and traverse the entire grid. Given the leg along a full side, you can construct the loop for (n+2)x(n+2) grid, given the loop for nxn grid as under.

• (Cornell) Two people have two consecutive natural numbers pasted on their heads, which they can't see but the other person can see. First person starts by asking the other if she knows what her number is. If she says yes, game ends. If she says no, she asks the first person if he knows his number. And so on. Does the game ever end? Sometimes? Never? Always?